#include <stdio.h>
#include <stdlib.h>

/**
 * 【线性链表】
 * 相关问题：
 *
 *
## 参数传递方式的区别

在您的程序中，`Sqlist *L` 和 `Sqlist L` 是两种不同的参数传递方式：

### Sqlist *L（指针传递）
- **含义**：传递的是顺序表结构体的指针（地址）
- **特点**：
  - 实际传递的是结构体的内存地址
  - 函数内可以直接修改原结构体的内容
  - 节省内存，不需要复制整个结构体

### Sqlist L（值传递）
- **含义**：传递的是顺序表结构体的副本
- **特点**：
  - 实际传递的是结构体的一个完整拷贝
  - 函数内无法修改原结构体的内容
  - 需要复制整个结构体，占用更多内存

## 使用场景分析

### 使用 Sqlist *L 的函数：
```c
int InitList_Sq(Sqlist *L)          // 需要初始化结构体内容
int DestroyList_Sq(Sqlist *L)       // 需要释放内存并修改结构体
int ClearList_Sq(Sqlist *L)         // 需要修改length字段
int ListInsert_Sq(Sqlist *L, int i, ElemType e)  // 需要修改表内容和长度
int ListDelete_Sq(Sqlist *L, int i, ElemType *e) // 需要修改表内容和长度
```

### 使用 Sqlist L 的函数：
```c
int ListEmpty_Sq(Sqlist L)          // 只需要读取length字段
int ListLength_Sq(Sqlist L)         // 只需要读取length字段
int GetElem_Sq(Sqlist L, int i, ElemType *e)     // 只需要读取元素
int LocateElem_Sq(Sqlist L, ElemType e, int (*compare)(ElemType, ElemType)) // 只需要查找元素
int ListTraverse_Sq(Sqlist L, int (*visit)(ElemType)) // 只需要遍历元素
```

## 选择原则

1. **需要修改原结构体时使用指针传递** (`Sqlist *L`)
   - 初始化、销毁、插入、删除等修改操作

2. **只需要读取结构体内容时使用值传递** (`Sqlist L`)
   - 查询、遍历等只读操作

3. **性能考虑**
   - 指针传递节省内存和复制开销
   - 值传递对小结构体影响不大，但更安全（不会意外修改原数据）

在您的代码中，这种区分使用是非常合理的，既保证了数据安全，又满足了不同操作的需求。

 */

// 定义状态码和常量
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INIT_SIZE 100 // 顺序表初始容量
#define LISTINCREMENT 10   // 顺序表扩容增量

// 定义元素类型（可根据需要修改）
typedef int ElemType;

// 顺序表结构定义
typedef struct
{
  ElemType *elem; // 存储空间基地址
  int length;     // 当前顺序表长度
  int listsize;   // 当前分配的存储容量
} Sqlist;

// 函数声明
int InitList_Sq(Sqlist *L);
int DestroyList_Sq(Sqlist *L);
int ClearList_Sq(Sqlist *L);
int ListEmpty_Sq(Sqlist L);
int ListLength_Sq(Sqlist L);
int GetElem_Sq(Sqlist L, int i, ElemType *e);
int LocateElem_Sq(Sqlist L, ElemType e, int (*compare)(ElemType, ElemType));
int PriorElem_Sq(Sqlist L, ElemType cur_e, ElemType *pre_e);
int NextElem_Sq(Sqlist L, ElemType cur_e, ElemType *next_e);
int ListInsert_Sq(Sqlist *L, int i, ElemType e);
int ListDelete_Sq(Sqlist *L, int i, ElemType *e);
/**
 * 遍历顺序表中的每个元素并调用访问函数处理
 * params:
 *   L: 待遍历的顺序表
 *   visit: 函数指针，指向用于处理每个元素的访问函数
 * return: 操作成功返回OK(1)，访问函数返回0时提前结束并返回ERROR(0)
 */
int ListTraverse_Sq(Sqlist L, int (*visit)(ElemType));
int ListExpand_Sq(Sqlist *L); // 扩容函数
void MergeList_Sq(Sqlist *La, Sqlist *Lb, Sqlist *Lc);

// 遍历访问函数示例
int visit(ElemType e)
{
  printf("%d ", e);
  return OK;
}

// 1. 初始化顺序表
int InitList_Sq(Sqlist *L)
{
  L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  if (!L->elem)
  {
    return OVERFLOW;
  }
  L->length = 0;
  L->listsize = LIST_INIT_SIZE;
  return OK;
}

// 2. 销毁顺序表
int DestroyList_Sq(Sqlist *L)
{
  if (L->elem)
  {
    free(L->elem);
    L->elem = NULL;
  }
  L->length = 0;
  L->listsize = 0;
  return OK;
}

// 3. 清空顺序表
int ClearList_Sq(Sqlist *L)
{
  L->length = 0;
  return OK;
}

// 4. 判断顺序表是否为空
int ListEmpty_Sq(Sqlist L)
{
  return L.length == 0;
}

// 5. 获取顺序表长度
int ListLength_Sq(Sqlist L)
{
  return L.length;
}

// 6. 获取指定位置的元素
int GetElem_Sq(Sqlist L, int i, ElemType *e)
{
  if (i < 1 || i > L.length)
  {
    return ERROR;
  }
  *e = L.elem[i - 1];
  return OK;
}

// 比较函数示例
int compare(ElemType a, ElemType b)
{
  return a == b;
}

// 7. 查找元素位置
int LocateElem_Sq(Sqlist L, ElemType e, int (*compare)(ElemType, ElemType))
{
  for (int i = 0; i < L.length; i++)
  {
    if (compare(L.elem[i], e))
    {
      return i + 1; // 返回位置（从1开始）
    }
  }
  return 0; // 未找到
}

// 8. 获取元素的前驱
int PriorElem_Sq(Sqlist L, ElemType cur_e, ElemType *pre_e)
{
  int pos = LocateElem_Sq(L, cur_e, compare);
  if (pos <= 1)
  {
    return ERROR; // 第一个元素或无此元素
  }
  *pre_e = L.elem[pos - 2];
  return OK;
}

// 9. 获取元素的后继
int NextElem_Sq(Sqlist L, ElemType cur_e, ElemType *next_e)
{
  int pos = LocateElem_Sq(L, cur_e, compare);
  if (pos == 0 || pos == L.length)
  {
    return ERROR; // 最后一个元素或无此元素
  }
  *next_e = L.elem[pos];
  return OK;
}

// 10. 扩容函数
int ListExpand_Sq(Sqlist *L)
{
  ElemType *newbase = (ElemType *)realloc(L->elem,
                                          (L->listsize + LISTINCREMENT) * sizeof(ElemType));
  if (!newbase)
  {
    return OVERFLOW;
  }
  L->elem = newbase;
  L->listsize += LISTINCREMENT;
  return OK;
}

// 11. 插入元素
int ListInsert_Sq(Sqlist *L, int i, ElemType e)
{
  if (i < 1 || i > L->length + 1)
  {
    return ERROR;
  }

  // 检查是否需要扩容
  if (L->length >= L->listsize)
  {
    if (ListExpand_Sq(L) == OVERFLOW)
    {
      return OVERFLOW;
    }
  }

  // 将插入位置后的元素后移，使用指针算术
  ElemType *q = &(L->elem[i - 1]);
  for (ElemType *p = &(L->elem[L->length - 1]); p >= q; --p)
  {
    *(p + 1) = *p;
  }
  *q = e;
  ++L->length;
  return OK;
}

// 12. 删除元素
int ListDelete_Sq(Sqlist *L, int i, ElemType *e)
{
  if (i < 1 || i > L->length)
  {
    return ERROR;
  }
  ElemType *p = &(L->elem[i - 1]);

  *e = *p; // 保存被删除的元素，需要返回给main函数展示删除掉的元素

  // 将删除位置后的元素前移，使用指针算术
  for (ElemType *q = p; q < &(L->elem[L->length - 1]); q++)
  {
    *q = *(q + 1);
  }

  --L->length;
  return OK;
}

// 13. 遍历顺序表
int ListTraverse_Sq(Sqlist L, int (*visit)(ElemType))
{
  for (int i = 0; i < L.length; i++)
  {
    if (!visit(L.elem[i]))
    {
      return ERROR;
    }
  }
  printf("\n");
  return OK;
}
// 14. 合并两个有序表
void MergeList_Sq(Sqlist *La, Sqlist *Lb, Sqlist *Lc)
{
  ElemType *pa, *pb, *pc;
  ElemType *pa_last, *pb_last;
  // 初始化指针 pa, pb，分别指向 La 和 Lb 的第一个元素
  pa = La->elem;
  pb = Lb->elem;

  // 初始化 Lc 的大小，并分配内存空间
  Lc->listsize = Lc->length = La->length + Lb->length;
  Lc->elem = (ElemType *)malloc(Lc->listsize * sizeof(ElemType));
  if (!Lc->elem)
  {
    exit(OVERFLOW); // 内存分配失败，退出程序
  }
  pc = Lc->elem;                       // 初始化 pc，指向 Lc 的第一个元素
  pa_last = &La->elem[La->length - 1]; // 等价于 La->elem + La->length - 1
  pb_last = &Lb->elem[Lb->length - 1]; // 等价于 Lb->elem + Lb->length - 1

  // 合并两个有序表，直到其中一个表的元素全部处理完
  while (pa <= pa_last && pb <= pb_last)
  {
    if (*pa <= *pb)
    {
      *pc++ = *pa++;
    }
    else
    {
      *pc++ = *pb++;
    }
  }

  // 复制剩余元素
  while (pa < &La->elem[La->length])
  {
    *pc++ = *pa++;
  }
  while (pb < &Lb->elem[Lb->length])
  {
    *pc++ = *pb++;
  }

  // 更新Lc的长度
  Lc->length = La->length + Lb->length;
}

// 15. 反转链表
void ReverseList_Sq(Sqlist *L)
{
  if (L == NULL || L->length <= 1)
    return; // 空链表或只有一个元素，无需反转

  ElemType *p = L->elem;
  ElemType *q = &L->elem[L->length - 1];
  while (p < q)
  {
    ElemType temp = *p;
    *p++ = *q;
    *q-- = temp;
  }
}

int main()
{
  Sqlist L;
  // 合并两个有序表
  Sqlist Lb, Lc;
  ElemType e;

  // 初始化顺序表
  printf("初始化顺序表...\n");
  if (InitList_Sq(&L) != OK)
  {
    printf("初始化失败！\n");
    return -1;
  }

  // 插入元素
  printf("插入元素 1, 2, 3, 4, 5...\n");
  for (int i = 1; i <= 5; i++)
  {
    ListInsert_Sq(&L, i, i);
  }
  ListInsert_Sq(&L, 6, 99); // 在位置6插入99

  // 遍历顺序表
  printf("顺序表元素: ");
  ListTraverse_Sq(L, visit);

  // 获取元素
  printf("获取第3个元素: ");
  if (GetElem_Sq(L, 3, &e) == OK)
  {
    printf("%d\n", e);
  }

  // 查找元素位置
  printf("元素4的位置: %d\n", LocateElem_Sq(L, 4, compare));

  // 删除元素
  printf("删除第2个元素...\n");
  ListDelete_Sq(&L, 2, &e);
  printf("被删除的元素: %d\n", e);

  // 再次遍历
  printf("删除后的顺序表: ");
  ListTraverse_Sq(L, visit);
  int result = InitList_Sq(&Lb);
  if (result != OK)
  {
    printf("初始化失败！\n");
    return -1;
  }
  printf("插入元素 6 12 18 24 30...\n");
  for (int i = 1; i <= 5; i++)
  {
    ListInsert_Sq(&Lb, i, i * 6);
  }
  printf("顺序表Lb元素: ");
  ListTraverse_Sq(Lb, visit);
  MergeList_Sq(&L, &Lb, &Lc);
  printf("合并后的顺序表Lc元素: ");
  ListTraverse_Sq(Lc, visit);
  ReverseList_Sq(&Lc);
  printf("反转后的顺序表Lc元素: ");
  ListTraverse_Sq(Lc, visit);

  // 清空顺序表
  printf("清空顺序表...\n");
  ClearList_Sq(&L);
  printf("顺序表是否为空: %s\n", ListEmpty_Sq(L) ? "是" : "否");

  // 销毁顺序表
  printf("销毁顺序表...\n");
  DestroyList_Sq(&L);

  return 0;
}